/**
 * https://leetcode-cn.com/problems/group-anagrams/
 * 字母异位词
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
 * @param strs
 */
const groupAnagrams = (strs: string[]): string[][] => {
  if (strs.length === 1) return [strs];
  const ans: string[][] = [];

  // 26个质数, 防止重复
  const prime = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101,
  ];

  const map: Record<number, string[]> = {};
  for (let s of strs) {
    let total = 0;
    for (let c of s) {
        total += prime[c.charCodeAt(0) - 97];
    }

    if (map[total]) {
      map[total].push(s);
    } else {
      const shareArr: string[] = [];
      shareArr.push(s);
      map[total] = shareArr;
      ans.push(shareArr);
    }
  }

  return ans;
};

const groupAnagrams3 = (strs: string[]): string[][] => {
  // 只有一项, 直接返回
  if (strs.length === 1) return [strs];

  const ans: string[][] = [];
  const len = strs.length;

  const map: Record<string, string[]> = {};
  for (let i = 0; i < len; i++) {
    // 排序
    const s = strs[i].split("").sort().join("");

    if (map[s]) {
      map[s].push(strs[i]);
    } else {
      // 创建数组
      const shareArr: string[] = [];
      map[s] = shareArr;
      shareArr.push(strs[i]);
      ans.push(shareArr);
    }
  }

  return ans;
};

// error 太耗内存
const groupAnagrams2 = (strs: string[]): string[][] => {
  // 只有一项, 直接返回
  if (strs.length === 1) return [strs];

  const ans: string[][] = [];
  const len = strs.length;

  /**
   * 获取字母所有的组合
   * @param str
   */
  const getCompose = (strs: string) => {
    const len = strs.length;
    const ret: string[] = [];
    // 判断是否已经选择过了
    const hasSelected = new Array(len).fill(false);
    const dfs = (level: number, str: string) => {
      if (level === len) {
        ret.push(str);
        return;
      }

      for (let i = 0; i < len; i++) {
        if (!hasSelected[i]) {
          // 如果还没有被选过
          hasSelected[i] = true;
          dfs(level + 1, str + strs[i]);
          // 恢复
          hasSelected[i] = false;
        }
      }
    };

    dfs(0, "");
    return ret;
  };

  let map: Record<string, string[]> = {};

  for (let i = 0; i < len; i++) {
    const s = strs[i];
    if (s === "") {
      // 空串
      if (map.empty) {
        map.empty.push(s);
      } else {
        const empty: string[] = [];
        map.empty = empty;
        ans.push(empty); // 放入结果中
        empty.push(s);
      }
      continue;
    }

    // 已经映射过了
    if (map[s]) {
      map[s].push(s);
    } else {
      // 创建映射
      const sArr = getCompose(s);
      // 所有组合的共用一个数组
      let arr: string[] = [];
      sArr.forEach((s) => {
        map[s] = arr;
      });

      // 把当前项也放入数组中
      arr.push(s);

      // 放入结果中
      ans.push(arr);
    }
  }

  return ans;
};

// console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat", "", ""]));
console.log(
  groupAnagrams([
    "cab",
    "tin",
    "pew",
    "duh",
    "may",
    "ill",
    "buy",
    "bar",
    "max",
    "doc",
  ])
);
